package com.hy.study.practice.sort;

import java.util.Arrays;

/**
 * 基数排序 又叫桶排序 是以空间换时间的
 */
public class RadixSort {

    public static void main(String[] args) {
        int arr[]={3,2,3,4,5,2,14,5,56,6767,565,45};
        System.out.println("----------排序之前----------");
        System.out.println(Arrays.toString(arr));
        radixSort(arr);
        System.out.println("------------排序之后-----------");
        System.out.println(Arrays.toString(arr));

    }

    private static void radixSort(int arr[]) {
        //1.查询 数组中最高的位数
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int maxLength = (max + "").length();

        //先得出 个位 百位 千位 等值
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {//最多有几位 n 表示 位数被除数
            //定义一个桶 ，数字一共有10位 这里 10*arr.length长度的数组
            int[][] bucket = new int[10][arr.length];
            //用于记录每个桶中存放的实际数据
            int[] bucketElementCounts = new int[10];
            for (int j = 0; j < arr.length; j++) {
                int temp = arr[j];//取出每一个元素
                //找到这个元素对应的个数  十位 或者百位...
                int digitOfElement = temp / n % 10;
                //将数据放入桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = temp;
            }
            //按照桶的顺序，将数据放回到原来的数组中
            int index=0;
            for (int k = 0; k < bucketElementCounts.length; k++) {
                if(bucketElementCounts[k]!=0){
                    //说明 有数据
                    for (int m = 0; m < bucketElementCounts[k]; m++) {
                        arr[index++]=bucket[k][m];

                    }
                }
                bucketElementCounts[k] = 0;//将临时数组归0 方便下次使用。
            }
        }



    }
}
